package algotithm.acwing.dp.test2;

/**
 * @author zhouyanxiang
 * @Date 2021-03-2021/3/12-23:46
 * AcWing 2. 01背包问题

4 5
1 2
2 4
3 4
4 5

8

 */
import java.io.*;


public class Main {

    private static int n;
    private static int m;
    private static int[] v = new int[1010];
    private static int[] w = new int[1010];
    private static int[] f = new int[1010];

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] num = reader.readLine().split(" ");
        int n = Integer.parseInt(num[0]);
        int m = Integer.parseInt(num[1]);

        for (int i = 1; i <= n; i++) {
            String[] arr = reader.readLine().split(" ");
            v[i] = Integer.parseInt(arr[0]);
            w[i] = Integer.parseInt(arr[1]);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= v[i]; j--) {
                f[j] = Math.max(f[j],f[j - v[i]] + w[i]);
            }
        }
        writer.write(f[m] + "\n");
        writer.flush();
        writer.close();
        reader.close();
    }

}
